/**
 * Created by L.jp
 * Description:给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，
 * 路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。
 * User: 86189
 * Date: 2022-08-27
 * Time: 23:41
 */
public class Solution {
    public int minPathSum (int[][] matrix) {
        int n=matrix.length;
        int m=matrix[0].length;
        //dp[i][j]表示到达i,j位置的最短路径和
        int[][] dp=new int[n+1][m+1];
        dp[0][0]=matrix[0][0];
        //从第二列开始处理第一行
        for(int i=1;i<m;i++){
            dp[0][i]=matrix[0][i]+dp[0][i-1];
        }
        //从第二开始处理第一列
        for(int i=1;i<n;i++){
            dp[i][0]=matrix[i][0]+dp[i-1][0];
        }
        for(int i=1;i<n;i++){
            for(int j=1;j<m;j++){
                dp[i][j]=matrix[i][j]+(Math.min(dp[i - 1][j], dp[i][j - 1]));
            }
        }
        return dp[n-1][m-1];
    }
}
